public class isSymmetric {
    /**
     * 判断是否是对称二叉树
     */
    class TreeNode{
        int val;
        TreeNode(){}
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 关键函数部分
    public boolean method(TreeNode root){
        // 利用dfs
        if(root == null){
            return true;
        }
        return dfs(root.left, root.right);
    }
    public boolean dfs(TreeNode left, TreeNode right){
        if(left == null && right ==null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val!=right.val){
            return false;
        }
        // 除去上述的情况
        return dfs(left.right, right.left) && dfs(left.left, right.right);
    }


    public static void main(String[] args) {
        isSymmetric is = new isSymmetric();
        TreeNode node = is.new TreeNode(1);

        node.left = is.new TreeNode(2);
        node.right = is.new TreeNode(2);
        node.left.left = is.new TreeNode(4);
        node.left.right = is.new TreeNode(5);
        node.right.left = is.new TreeNode(5);
        node.right.right = is.new TreeNode(4);

        boolean t = is.method(node);
        System.out.println("t = " + t);
    }
}
